﻿#ifndef __L5_SEARCH_H_INCL__
#define __L5_SEARCH_H_INCL__

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

class L5_Search {
 public:
  L5_Search();
  virtual ~L5_Search();

  void DFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES], list<int> vertex_list, int nd_no);   //DFS初始化程序，graph为邻接矩阵，vertex_list为顶点表，nd_no为搜索的起点
  void BFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES], list<int> vertex_list, int nd_no);   //BFS初始化程序，graph为邻接矩阵，vertex_list为顶点表，nd_no为搜索的起点

  vector<int >  _vertex_flag;     //顶点访问标志

 private:
  void DFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i);  //DPF迭代,
  void BFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i);  //BFS

  vector<int> _vertex_stack;    //临时
  vector<int> _vertex_list;     //根据list的各元素顺序将各元素存在vector中，实现随机访问
  queue<int > _vertex_order;    //BFS时，访问过的节点，FIFO
  vector<int > m_v_visit_order; //按照访问节点的顺序保存节点

};

//补充
inline L5_Search::L5_Search(){
}

inline L5_Search::~L5_Search(){
}

//DFS初始化程序，graph为邻接矩阵，vertex_list为顶点表，nd_no为搜索的起点，新起点表示不同连通子图的起点
void L5_Search::DFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES], list<int> vertex_list, int nd_no){
  _vertex_list.assign(vertex_list.begin(), vertex_list.end() );     //将vertex_list的元素复制到_vertex_list中，实现随机访问
  _vertex_flag.assign(_vertex_list.size(), 0);                      //初始化顶点表访问标志位，0表示未访问
  vector<int>::iterator iter = find(_vertex_list.begin(), _vertex_list.end(), nd_no); //待补充，错误处理
  int i_start = iter - _vertex_list.begin();

  cout << "DFS起始节点:" <<_vertex_list[i_start] << endl;

  //根据起始顶点，遍历
  for (int i= i_start; i < _vertex_list.size(); i++ ){
    if (_vertex_flag[i] == 0) {
      cout << endl <<"新起点：" << _vertex_list[i] << endl;
      m_v_visit_order.clear();        //新的连通子图
      DFS_main(graph_adjm, i);
      cout << "DFS访问顺序为：";
      for (vector<int >::iterator iter = m_v_visit_order.begin(); iter != m_v_visit_order.end(); iter++ ){
        cout << * iter << "    ";
      }
    }
  }
  for (int i = 0; i < i_start; ){
    if (_vertex_flag[i] == 0) {
      cout << endl << "新起点：" << _vertex_list[i] << endl;
      m_v_visit_order.clear();        //新的连通子图
      DFS_main(graph_adjm, i);
      cout << "DFS访问顺序为：";
      for (vector<int >::iterator iter = m_v_visit_order.begin(); iter != m_v_visit_order.end(); iter++ ){
        cout << * iter << "    ";
      }
    }
  }

}

//BFS初始化程序，graph为邻接矩阵，vertex_list为顶点表，nd_no为搜索的起点
void L5_Search::BFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES], list<int> vertex_list, int nd_no){
  _vertex_list.assign(vertex_list.begin(), vertex_list.end() );     //将vertex_list的元素复制到_vertex_list中，实现随机访问
  _vertex_flag.assign(_vertex_list.size(), 0);    //初始化顶点表访问标志位，0表示未访问
  vector<int>::iterator iter = find(_vertex_list.begin(), _vertex_list.end(), nd_no); //待补充，错误处理
  int i_start = iter - _vertex_list.begin();

  cout << "BFS起始节点:" <<_vertex_list[i_start] << endl;

  //根据起始顶点，遍历
  for (int i= i_start; i < _vertex_list.size(); i++ ){
    if (_vertex_flag[i] == 0) {
      //_vertex_order.push(_vertex_list[i] );   //将该节点入栈
      _vertex_flag[i] = 1;
      cout  << endl <<"新起点：" << _vertex_list[i] << endl;
      BFS_main(graph_adjm, i);
    }
  }
  for (int i = 0; i < i_start; ){
    if (_vertex_flag[i] == 0) {
      cout << endl << "新起点：" << _vertex_list[i] << endl;
      DFS_main(graph_adjm, i);
    }
  }

}

//DFS迭代主程序，i 表示第i个顶点
void L5_Search::DFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i){
  _vertex_stack.push_back(_vertex_list[i] );   //将该节点入栈
  _vertex_flag[i] = 1;
  cout << _vertex_list[i] << "    ";                     //打印访问的节点
  m_v_visit_order.push_back(_vertex_list[i]);
  for (int j = 0; j < _vertex_list.size(); j++ ) {
    if (graph_adjm[i][j] != 0 && _vertex_flag[j] == 0){
      //如果关联矩阵的第(i-1)行和第(j-1)行所表示节点邻接，且第(j-1)列所表示的节点未访问则执行此步
      DFS_main(graph_adjm, j);
    }
  }

}

//BFS,i 表示第i个顶点,NEW:表示从该点进行BFS
void L5_Search::BFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i){
  for (int j = 0; j < _vertex_list.size(); j++ ) {
    //cout << "MX[" << i << "][" << j << "] = " << graph_adjm[i][j] << "@@";
    if (graph_adjm[i][j] != 0 && _vertex_flag[j] == 0){
      //如果关联矩阵的第(i-1)行和第(j-1)行所表示节点邻接，且第(j-1)列所表示的节点未访问则执行此步
      _vertex_order.push(j );   //
      _vertex_flag[j] = 1;
      cout << _vertex_list[j] << "    ";                     //打印访问的节点
    }
  }

  if(!_vertex_order.empty() ){
    int no_temp = _vertex_order.front();
    _vertex_order.pop();
    cout << endl << "NEW:" << _vertex_list[no_temp] << endl;
    BFS_main(graph_adjm, no_temp);
  }

}

#endif // __L5_SEARCH_H_INCL__

